동적 프로그래밍_{(r30 문단 편집)}

=== 컴퓨터 과학에서의 동적 프로그래밍 ===
상태기반의 문제를 재귀적으로 해석하는 방법은 너무나도 일반화 하기 쉬운 강력한 방법이었다. 이 문제를 최적제어 문제에만 쓰기 아까웠던 사람들은 다른 문제에도 사용하기 시작하였고 최적 경로, 그래프 탐색 문제등을 시작으로 동적 프로그래밍의 사상 아래에서 해결될 수 있음을 보였다.

이와 관련된 대표적인 예제는 동적 프로그래밍의 방법을 적용하여 피보나치 수열을 최적화 하는 문제가 있다. 아래의 코드는 Dictionary<int, int[]> 형태의 자료구조에 계산 값을 저장한 뒤, 중복된 계산식이 호출되면 해당 자료구조에서 이전에 계산된 값을 확인 후, 계산 값을 반환하여 불필요한 계산~~삽질~~을 처리하지 않게 한다.
{{{#!syntax cpp
Dictionary<int, int[]> dicFibo = new Dictionary<int, int[]>();

public int[] Getfibonacci(int n)
{
    if (n == 0)
    {
        if (!dicFibo.ContainsKey(0))
            dicFibo.Add(0, new int[] { 1, 0 });

return new int[] { 1, 0 };
    }
    else if (n == 1)
    {
        if (!dicFibo.ContainsKey(1))
            dicFibo.Add(1, new int[] { 0, 1 });

return new int[] { 0, 1 };
    }
    else
    {
        if (dicFibo.ContainsKey(n))
        {
            return dicFibo[n];
        }
        else
        {
            dicFibo[n] = new int[] { Getfibonacci(n - 1)[0] + Getfibonacci(n - 2)[0] , Getfibonacci(n - 1)[1] + Getfibonacci(n - 2)[1] };
            return dicFibo[n];
        }
    }
}
}}}

요약

문서 편집을 저장하면 당신은 기여한 내용을 CC BY-NC-SA 2.0 KR으로 배포하고 기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다. 이 동의는 철회할 수 없습니다.

비로그인 상태로 편집합니다. 로그인하지 않은 상태로 문서 편집을 저장하면, 편집 역사에 본인이 사용하는 IP(18.117.71.244) 주소 전체가 영구히 기록됩니다.

동적 프로그래밍(r30 문단 편집)

동적 프로그래밍_{(r30 문단 편집)}